﻿// Ant Counting POJ - 3046.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-3046

/*
有一天，贝西在蚂蚁山里探头探脑，看着蚂蚁们来来回回地觅食。
她发现很多蚂蚁都是兄弟姐妹，彼此无法区分。
她还发现，有时只有一只蚂蚁去觅食，有时几只，有时全部。
这就产生了大量不同组合的蚂蚁！

有点数学天赋的贝茜开始琢磨起来。贝西注意到，蜂巢里有 T（1 <= T <= 1,000）个蚂蚁家庭，
她把它们标为 1...T（共有 A 只蚂蚁）。
每个家庭有一定数量的蚂蚁 Ni (1 <= Ni <= 100)。

可以组成多少个大小为 S、S+1、......、B（1 <= S <= B <= A）的小组？

在观察一个蚂蚁群时，可以看到三个蚂蚁家族的集合是{1, 1, 2, 2, 3}，但很少按这个顺序排列。
蚂蚁行进的可能集合是

有 1 只蚂蚁的 3 个集合： {1} {2} {3}
有 2 只蚂蚁的 5 组 {1,1} {1,2} {1,3} {2,2} {2,3}
有 3 只蚂蚁的 5 组 {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
有 4 只蚂蚁的 3 组 {1,2,2,3} {1,1,2,2} {1,1,2,3}
有 5 只蚂蚁的 1 组 {1,1,2,2,3}

你的任务是根据上述数据计算可能的蚂蚁集合数。
输入
* 第 1 行：4 个空格分隔的整数： T、A、S 和 B

* 第 2...A+1 行：每行包含一个整数，即蜂巢中存在的蚂蚁类型
输出
* 第 1 行： 可创建的大小为 S...B（包括 S...B）的集合数量。像 {1,2} 这样的集合与 {2,1} 这样的集合相同，不应重复计算。
只打印该数字的后六位，不打印前导零或空格。


3 5 2 3
1
2
2
1
3

10


提示
输入细节：
三种类型的蚂蚁（1...3）；共有 5 只蚂蚁。可以制作多少套大小为 2 或 3 的蚂蚁？

输出细节：
5 组有两名成员的蚂蚁；另外 5 组有三名成员的蚂蚁
*/

const int N = 100010;
const int MOD = 1000000;
int dp[2][N];
int arr[N];
int t, a, s, b;


int main()
{
	cin >> t >> a >> s >> b;
	int curr = 1;
	int prev = 0;
	dp[0][0] = 1; 
	for (int i = 0; i < a; i++) {
		int tmp; cin >> tmp;
		arr[tmp]++;
	}

	for (int i = 1; i <= t; i++) {
		int duan = 1;
		for (int j = 0; j <= a; j++) {
			if (j > arr[i])
				dp[curr][j] = (dp[prev][j] + dp[curr][j - 1] - dp[prev][j - 1 - arr[i]]+ MOD)%MOD;
			else if( j > 0)
				dp[curr][j] = dp[prev][j] + dp[curr][j - 1];
			else {
				dp[curr][j] = dp[prev][j];
			}

			dp[curr][j] = (dp[curr][j]+MOD) % MOD;
		}

		swap(curr, prev);
	}
	
	int ans = 0;
	for (int i = s; i <= b; i++) {
		ans += dp[prev][i];
		ans %= MOD;
	}

	cout << ans << endl;


	return 0;
}
